package com.javabasic.algorithm.helloInterview;

/**
 * @Author xiongmin
 * @Description TODO
 * @Date 2019/9/18 20:43
 * @Version 1.0
 **/
public class Test {


    public static void main(String[] args) {

    }

    public static void caculate(int n, int m, int[] arr) {

    }

    /**
     * @param n   表示n名罪犯
     * @param c   表示选择人数
     * @param t   表示选择c人的最大允许罪行值
     * @param arr 表示n名罪犯的罪行值
     */
    public static int selectWays2(int n, int c, int t, int[] arr) {
        int temp, result = 0;
        boolean flag;
        for (int i = 0; i < n; i++) {
            temp = 0;
            flag = true;
            for (int j = 0; j < c; j++) {
                temp += arr[i];
                if (temp > t) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                result++;
            }
        }
        return result;
    }

    /**
     * @param n   表示n名罪犯
     * @param c   表示选择人数
     * @param t   表示选择c人的最大允许罪行值
     * @param arr 表示n名罪犯的罪行值
     *
     * 算法复杂度O(N)
     */
    public static int selectWays(int n, int c, int t, int[] arr) {
        int[] dp = new int[n];
        dp[0] = arr[0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1] + arr[i];
        }
        int result = 0;
        for (int i = c-1; i < n; i++) {
            if (dp[i] - dp[i-c+1] <= t) {
                result++;
            }
        }
        return result;
    }
}
